package 二叉树题目.二叉搜索树的最近公共祖先;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        // write code here
        List<Integer> listP = new ArrayList<>();
        List<Integer> listQ = new ArrayList<>();
        listP = getPath(root, p);  // 7 1 4 5
        listQ = getPath(root, q);  // 7 12 1
        // 题目要求是最近的公共祖先
        int ret = 0;
        for (int i = 0; i < listQ.size() && i < listP.size(); i++) {

            // 此处一定要拆箱 不然超过 -128~127 比较的就是地址了;
            if (listP.get(i).intValue() == listQ.get(i).intValue()) {
                ret = listQ.get(i);
            } else {
                break;
            }

        }
        return ret;


    }

    public List<Integer> getPath(TreeNode root, int val) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur.val != val) {
            list.add(cur.val);
            if (cur.val < val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        list.add(cur.val);
        return list;
    }
}
